/**
 * @author LKQ
 * @date 2022/3/5 13:24
 * @description 二维数组前缀和，原理即面积相减，但要注意前缀和数组长度为 m+1, n+1这样方便求值
 */
public class Solution {
    public static void main(String[] args) {

    }
    int[][] dp;
    public Solution(int[][] matrix) {
        int m = matrix.length;
        if (m > 0) {
            int n = matrix[0].length;
            dp = new int[m + 1][n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 二维数组前缀和
                    dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + matrix[i][j];
                }
            }
        }

    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        // 这里的+1是因为dp下标从1到n
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1 ] - dp[row2 + 1][col1] + dp[row1][col1];
    }
}
